package q41

import "fmt"

const INF =-1
func firstMissingPositive(nums []int) int {

	maybe:=[][2]int{
		[2]int{1,INF},
	}

	for _,num:=range nums{
		if num<=0{
			continue
		}

		for i,ran:=range maybe{
			//在此范围内
			if compare(num,ran[0])>=0 && compare(num,ran[1])<=0 {
				//进行分割
				left:=[2]int{ran[0],num-1}
				right:=[2]int{num+1,ran[1]}

				debugLog(fmt.Sprintf("分割数:%d,%d,分割前：%v,分割为：%v,%v\n",i,num,ran,left,right))

				if compare(left[0],left[1])>0 && compare(right[0],right[1])>0{
					//删除 maybe[i]
					x:=[][2]int{}
					for j,y:=range maybe{
						if j==i{
							continue
						}
						x=append(x, y)
					}
					debugLog(fmt.Sprint("all-"))
					maybe=x
				}else if compare(left[0],left[1])>0{
					//只加right
					debugLog(fmt.Sprint("right+"))
					maybe[i]=right
				}else if compare(right[0],right[1])>0{
					//只加left
					debugLog(fmt.Sprint("left+"))
					maybe[i]=left
				}else{
					//都加
					maybe[i]=left
					if i>= len(maybe)-1{
						debugLog(fmt.Sprint("all+one"))
						//最后一个
						maybe=append(maybe, right)
					}else{
						debugLog(fmt.Sprint("all+"))
						debugLog(fmt.Sprintf("+之前:%v",maybe))

						x:=append([][2]int{},maybe[:i+1]...)
						debugLog(fmt.Sprintf("x:%v",x))
						x=append(x, right)
						debugLog(fmt.Sprintf("x:%v",x))
						x=append(x, maybe[i+1:]...)
						debugLog(fmt.Sprintf("maybe:%v",maybe[i+1:]))
						maybe=x
						debugLog(fmt.Sprintf("+之后:%v",maybe))

					}

				}
				debugLog(fmt.Sprintf("从 %d 分割后: %v\n",num,maybe))
				//

				break
			}
		}
	}

	return maybe[0][0]
}

//比较-1：小于，0：相等，1：大于
func compare(x,y int)int{
	if y==INF{
		return -1
	}
	if x==y{
		return 0
	}
	if x>y{
		return 1
	}
	return -1
}

var debug=false

func debugLog(content string){
	if debug{
		fmt.Println(content)
	}
}